package b_sorting_advance.a_merge_sort;

import org.junit.Test;
import utils.ArrayGeneric;
import utils.sorting_helper.SortingTest;

/**
 * @Author: DeLucia
 * @Description:
 * @Date: 2019/1/22 22:28.
 */
@SuppressWarnings("unchecked")
public class MergeSortRevert extends SortingTest {
    /**
     * 归并排序 - 可以将空间复杂度降至O（1）的手摇算法（内存反转）
     * 平均时间复杂度	        最坏时间复杂度	    空间复杂度	是否稳定
     * O(nlogn)~O(n*nlogn)	O (n*nlogn)	        O（1）	    是
     * <p>
     * 适合内存小的电脑，但是大大牺牲了时间性能 所以意义不大
     *
     * @param arr
     */
    @Override
    public void sort(ArrayGeneric arr) {
        mergeSortRevert(arr, 0, arr.length() - 1);
    }

    private void mergeSortRevert(ArrayGeneric a, int left, int right) {
        if (right - left <= 15) {
            insertionSort(a, left, right);
            return;
        }
        int mid = (left + right) / 2;
        mergeSortRevert(a, left, mid);// left-mid有序
        mergeSortRevert(a, mid + 1, right); // mid + 1-right有序
        if (a.get(mid).compareTo(a.get(mid + 1)) > 0) {
            merge(a, left, mid, right); // 将 left-mid和mid+1-right合并成一个有序的数组
        }
        // 在合并的时候采用了手摇算法
        // 不再使用临时数组交换 因此降低了空间复杂度
    }

    /**
     * 数组的将left-mid和mid+1-right合并成一个有序数组
     * @param a 待合并数组
     * @param left
     * @param mid
     * @param right
     */
    private void merge(ArrayGeneric a, int left, int mid, int right) {
        int i = left; // 左边的扫描位置
        int j = mid + 1; //右边的扫描位置
        // index从mid+1处向右扫描
        // 扫描的时候如果i<=j就左边指针右移，遇到i>j就停下，此时i处就是手摇算法的left位置
        // 扫描的时候如果j比i还小，就右边指针右移，直到j>=i时停止 这时j-1就是手摇算法的right位置
        // 这时将i..index-1和index..j-1互换
        while (i < j && j <= right) {
            while (i < j && a.get(i).compareTo(a.get(j)) <= 0) i++;
            int index = j;
            while (j <= right && a.get(j).compareTo(a.get(i)) < 0) j++;
            convert(a, i, index - 1, j - 1); // 手摇算法
            // 互换后i前进j-index的位置
            i += j - index;
        }
    }

    /**
     * 手摇算法
     *
     * 将数组的left-mid和mid+1-right两部分互换
     * 比如讲HELLOWORLD交换成WORLDHELLO 分成三步
     * 1.翻转HELLO ——》 OLLEH
     * 2.翻转WORLD ——》 DLROW
     * 3.整体翻转 OLLEHDLROW--》WORLDHELLO
     * @param a     输入数组
     * @param left
     * @param mid
     * @param right
     */
    private void convert(ArrayGeneric a, int left, int mid, int right) {
        reverse(a, left, mid); // 反转左侧
        reverse(a, mid + 1, right); //反转右侧
        reverse(a, left, right); // 整体翻转
    }

    /**
     * 数组倒转
     * @param a
     * @param left
     * @param right
     */
    private void reverse(ArrayGeneric a, int left, int right) {
        for (; left < right; left++, right--) {
            a.swap(left, right);
        }
    }

    /**
     * 当递归到数组规模小于16的时候
     * 为了提高性能改用插入排序
     *
     * @param arr
     * @param left
     * @param right
     */
    private void insertionSort(ArrayGeneric arr, int left, int right) {
        for (int i = left + 1; i <= right; i++) {
            Comparable e = arr.get(i);
            int j;
            for (j = i; j > left && arr.get(j - 1).compareTo(e) > 0; j--) {
                arr.put(j, arr.get(j - 1));
            }
            arr.put(j, e);
        }
    }

    @Test
    public void testing() {
//        new MergeSortRevert().testSorting("手摇算法的归并排序", MergeSort.getRandomIntegerArray(2000, 0, 2000));
        ArrayGeneric<Integer> arrayGeneric = MergeSortRevert.getRandomIntegerArray(10, 0, 10);
        System.out.println(arrayGeneric);
        convert(arrayGeneric,0,3,9);
        System.out.println(arrayGeneric);
    }
}